package panel.viewSpots.navigation
{
	import flashx.textLayout.elements.ListElement;
	
	public class PathSeek
	{
		private var _pathList:Array = [];
		private var _nodeList:Array = [];
		private var _nodeIndexList:Array = [];
		private var _normalPathList:Array = [];//存储经过路线
		private var _normalPathSpotList:Array = [];//存储经过的景点
		private var _shortPath:Object = {};
		
		private var _removePath:Array = [];
		private var _addPath:Array = [];
		private var _changeIndex:int//因为处理添加环线中的路线而造成的路线数组位置修改
		private var _changePathIndex:int;
		public function PathSeek()
		{
			init();
		}
		
		private function init():void
		{
			_shortPath.cost = 999;
			_pathList = [
				generateNodePath("0","1",5),
				generateNodePath("1","2",10),
				generateNodePath("2","a",20),
				generateNodePath("a","7",5),
				generateNodePath("a","4",3),
				generateNodePath("7","3",5),
				generateNodePath("4","3",12),
				generateNodePath("6","8",10),
				generateNodePath("5","a",4),
				generateNodePath("4","5",4),
//				generateNodePath("4","7",3),//test
//								generateNodePath("c","b",4),//test
				generateNodePath("3","6",10)
			];
			
			_normalPathList = [
				"0","1","2","a","7","3","6","8"
			];
			
			getPathSpotList();
			generateNodeIndexList();//找出路线中的所有结点
			generateNodeList();//生成程序需要的结点数据
		}
		
		private function getPathSpotList():void
		{
			for(var i:int=0;i<_normalPathList.length;i++)
			{
				if(_normalPathList[i].charCodeAt(0) < 58)
				{
					_normalPathSpotList.push(_normalPathList[i]);
				}
			}
		}
		
		private function removePathSpotByIndex(index:String):void
		{
			for(var i:int=0;i<_normalPathSpotList.length;i++)
			{
				if(_normalPathSpotList[i] == index)
				{
					_normalPathSpotList.splice(i,1);
				}
			}
		}
		
		public function setStartIndex(startIndex:String):void
		{
			var isFind:Boolean;
			for(var i:int=0;i<_normalPathList.length;i++)
			{
				if(_normalPathList[i] == startIndex)
				{
					isFind = true;
					_normalPathList.splice(0,i);
				}
			}
			if(!isFind)
			{
				addPathNode(startIndex);
			}
			
		}
		
		public function getNormalPath():Array
		{
			return _normalPathList;
		}
		/**
		 *判断点是否处于一个环路线中 
		 * @param spotIndex
		 * @return 
		 * 
		 */		
		private function isCirclePath(spotIndex:String,pathCost:Number,oriPath:Array,circleIndex:String):Array
		{
			var findNum:int;
			var index:String;
			var nextSpotIndex:String;
			for(var i:int=0;i<_normalPathList.length;i++)
			{
				findNum = 0;
				index = _normalPathList[i];
				for(var j:int=0;j<_normalPathList.length;j++)
				{
					if(_normalPathList[j] == index)
					{
						++ findNum;
						if(findNum == 2)
						{
							var node:nodeStruct = seekSpotNode(j + 1);
							if(node)
							{
							nextSpotIndex = node.index;
							}
						    break;	
						}
					}
				}
				if(nextSpotIndex != null) break;
			}
			_changeIndex = 0;
			for(var k:int=i;k<j;k++)
			{
				if(_normalPathList[k] == circleIndex)
				{
					if(comuteNowAndNextDis(spotIndex,index,nextSpotIndex,pathCost,circleIndex))
					{
					_normalPathList.splice(i + Math.ceil((j-i)/2) + 1,int((j-i)/2));
					_changeIndex = int((j-i)/2);
					oriPath = _shortPath.path;
					trace("修改之后的路线：" + _normalPathList);
					return oriPath;
					}
					break;
				}
			}
			return oriPath;
		}
		
		private function seekSpotNode(index:int,sortType:int = 1):nodeStruct
		{
			var nodeIndex:String = _normalPathList[index];
			if(nodeIndex == null) return null;
			var node:nodeStruct = seekNode(_normalPathList[index]);
			if(node.nodeType == 2)
			{
				_changePathIndex = index;
				return node;
			}else
			{
				return seekSpotNode(index + sortType);
			}
		}
		
		/**
		 *计算环线中原环线到环线开始点的下一点的距离与该点到环线开始点的下一点的距离 
		 * 点得先修改掉 普通路线 并且将新增加路线 添加出来
		 */		
		private function comuteNowAndNextDis(spotIndex:String,circleStartIndex:String,nextSpotIndex:String,pathCost:Number,oriIndex:String):Boolean
		{
//			计算原环线中下一点的距离
			var circleOriCost:Number = pathCost;
			startSeek(circleStartIndex,nextSpotIndex);
			circleOriCost = circleOriCost + _shortPath.cost;
			startSeek(spotIndex,oriIndex);
			circleOriCost = circleOriCost + _shortPath.cost
			
//			计算当前点到下一点的距离
			startSeek(spotIndex,nextSpotIndex);
			if(_shortPath.cost > circleOriCost)
			{
				return false;
			}else 
			{
				return true;
			}
		}
		
		private function seekPathInfo(startIndex:String,endIndex:String):nodePathStruct
		{
			var len:int = _pathList.length;
			var nodePath:nodePathStruct;
			for(var i:int=0;i<len;i++)
			{
				nodePath = _pathList[i];
				if(nodePath.startIndex == startIndex || nodePath.endIndex == endIndex)
				{
					return nodePath;
				}
			}
			return null;
		}
		
		/**
		 *获取添加点与路线中所有点的距离，然后比较，到最近点和最近点相邻点最近的点和原路返回的方式哪个更短 
		 * @param index
		 * 
		 */		
		public function addPathNode(index:String):void
		{
			_removePath = [];
			_addPath = [];
//			找添加点到路线中所有点的距离
			var len:int = _normalPathSpotList.length;
			var allPathList:Array = [];
				var node:nodeStruct;
			for(var i:int=0;i<len;i++)
			{
				node = seekNodeByIndex(_normalPathSpotList[i]);
				if(!node || node.nodeType == 1) continue;
				startSeek(index,_normalPathSpotList[i]);
				allPathList.push({cost:_shortPath.cost,path:_shortPath.path,index:_normalPathSpotList[i]});
			}
			
//			比较添加点到前后两个点的最短距离
			var minCost:uint = 99999999;
			var minIndex:int;
			var allLen:int = allPathList.length;
			var pathType:int = 1;//type为1 表示从该点出发 再从该店回来
			var minPathType:int = pathType;
			var minPathList:Array;//最小路径
			for(i=0;i<allLen;i++)
			{
				if(i == 0 || i == allLen - 1)
				{
					if(minCost > allPathList[i].cost)
					{
						minCost = allPathList[i].cost;
						minIndex = i;
					}
					continue;
				}else
				{
					if(allPathList[i].cost + allPathList[i + 1].cost > 2 * allPathList[i].cost)
					{
						allPathList[i].cost = allPathList[i].cost * 2;
						pathType = 1;
					}else
					{
						allPathList[i].cost = allPathList[i].cost + allPathList[i + 1].cost;
						pathType = 2;
					}
					if(minCost > allPathList[i].cost)
					{
						minCost = allPathList[i].cost;
						minIndex = i;
						minPathType = pathType;
					}
				}
			
			}
			
//		获得添加位置 并添加到适当位置
			_normalPathSpotList.splice(minIndex,index);
			if(minPathType == 1)
			{
				_addPath = [];
				minPathList = isCirclePath(index,minCost/2,allPathList[minIndex].path,allPathList[minIndex].index);
//				minPathList = allPathList[minIndex].path;
				_addPath = _addPath.concat(minPathList);
				_addPath.reverse();
				for(var m:int=1;m<_addPath.length;++m)
				{
					_normalPathList.splice(minIndex + 1 + _changeIndex,0,_addPath[m]);
				}
				if(_changeIndex != 0)
				{
					_addPath.push(_normalPathList[minIndex +　1]);
				}
			}else
			{
				minPathList = cancatPath(allPathList[minIndex].path,allPathList[minIndex + 1].path);
				_addPath = minPathList;
				for(m=0;m<minPathList.length;++m)
				{
					_normalPathList.splice(minIndex + 1,0,minPathList[m]);
				}
			}
			trace("addPath:" + _addPath);
			trace("addPath后的normalpath:" + _normalPathList);
		
		}
		
		private function spliceRemovePath(startIndex:String,endIndex:String):void
		{
			_removePath = [];
			var isStart:uint = 0;
			for(var i:int=0;i<_normalPathList.length;i++)
			{
				if(_normalPathList[i] == startIndex || _normalPathList[i] == endIndex)
				{
						++ isStart;
				}
				if(isStart == 2)
				{
					_removePath.push(_normalPathList[i]);
			trace("remove path" + _removePath);
					return;
				}
				else if(isStart > 0)
				{
					_removePath.push(_normalPathList[i]);
				}
			}
		}
		
		private function cancatPath(frontList:Array,backList:Array):Array
		{
			spliceRemovePath(frontList.pop(),backList.pop());
			frontList.reverse();
			backList.shift();
			backList.pop();
			var list:Array = frontList.concat(backList);
			return list;
		}
		
		public function removePathNode(index:String):void
		{
			_removePath = [];
			_addPath = [];
			var len:int = _normalPathList.length;
			for(var i:int=0;i<len;i++)
			{
				if(_normalPathList[i] == index)
				{
					if(i == 0)//去掉点为起始点的情况
					{
						_removePath.push(_normalPathList[0]);
						_removePath.push(_normalPathList[1]);
						_normalPathList.splice(0,1);
					}else if(i == len - 1)//去掉点为结束点情况
					{
						_removePath.push(_normalPathList[len - 2]);
						_removePath.push(_normalPathList[len - 1]);
						_normalPathList.splice(len - 1,1);
					}else
					{
						if(_normalPathList[i - 1] == _normalPathList[i + 1])//如果是回头路线
						{
//					1.先找上个经过的和将要去的景点，把这之间的所有路线都删掉 2.获取这两个景点之间的路线
							var startNode:nodeStruct = seekSpotNode(i - 1,-1);
							var endNode:nodeStruct = seekSpotNode(i + 1);
							_removePath = seekCircle(startNode.index,endNode.index);
							startSeek(startNode.index,endNode.index);
							_addPath = _shortPath.path;
							_addPath.reverse();
							for(var n:int=1;n<_addPath.length;++n)
							{
							_normalPathList.splice(_changeIndex + 1,0,_addPath[n]);
							}
						}else
						{
							var endSpotIndex:String = seekSpotNode(i + 1).index;
							startSeek(seekSpotNode(i - 1,-1).index,endSpotIndex);
							_removePath = _normalPathList.splice(_changePathIndex,_shortPath.path.length);
							for(var m:int=0;m<_shortPath.path.length;++m)
							{
								_normalPathList.splice(_changePathIndex +　m,0,_shortPath.path[m]);
							}
							_addPath = _shortPath.path;
						}
					}
					break;
				}
			}
			trace("removeList:" + _removePath);
			trace("remove后的normalPathList：" +　_normalPathList);
			removePathSpotByIndex(index);
		}
		
		private function seekCircle(circleStartIndex:String,circleEndIndex:String):Array
		{
			var endIndex:int;
			var startIndex:int;
			for(var i:int=0;i<_normalPathList.length;i++)
			{
				if(_normalPathList[i] == circleStartIndex)
				{
					startIndex = i;
				}else if(_normalPathList[i] == circleEndIndex)
				{
					endIndex = i;
				}
			}
			return _normalPathList.splice(startIndex,endIndex - startIndex);
		}
		
		/**
		 *找寻两点间最小的路线 
		 * @param startIndex
		 * @param endIndex
		 * 
		 */		
		public function startSeek(startIndex:String,endIndex:String):void
		{
			_shortPath.cost = 999;
			seekPath(seekNodeByIndex(startIndex),startIndex,endIndex);
		}
		
		private function seekPath(node:nodeStruct,startIndex:String,endIndex:String):void
		{
			if(!node) return;
			node.parentNodeIndex = startIndex;
			node.isVisiting = true;
			for(var i:int=0;i<node.linkNodeList.length;i++)
			{
				if(node.index == endIndex)
				{
					generatePath(node);//生成路线 并且继续遍历下个相连的结点
					trace("---------------------" + i);
					node.isVisiting = false;
					return;
				}
				else if(node.linkNodeList[i].index != startIndex)
				{
					var nodeTemp:nodeStruct = seekNodeByIndex(node.linkNodeList[i].index);
					if(!nodeTemp)
					{
						continue;
					}
					else if(nodeTemp.isVisiting == true)
					{
						continue;
					}else
					{
						seekPath(nodeTemp,node.index,endIndex);
					}
				}
			}
			node.isVisiting = false;
		}
		
		private function generatePath(node:nodeStruct):void
		{
			var pathList:Array = [];
			var tempNode:nodeStruct = node;
			var cost:uint = 0;
			while(tempNode.index != tempNode.parentNodeIndex)
			{
				pathList.unshift(tempNode.index);
				cost += seekPathCost(tempNode.linkNodeList,tempNode.parentNodeIndex);
//				trace("path:" + tempNode.index);
				tempNode = seekNodeByIndex(tempNode.parentNodeIndex);
			}
			cost += seekPathCost(tempNode.linkNodeList,tempNode.parentNodeIndex);
			pathList.unshift(tempNode.index);
//			trace("path:" + tempNode.index + "time:" + cost);
			if(_shortPath.cost > cost)
			{
				_shortPath.cost = cost;
				_shortPath.path = pathList;
			}
		}
		
		private function seekPathCost(list:Array,index:String):uint
		{
			for(var i:int=0;i<list.length;i++)
			{
				if(list[i].index == index)
				{
					return list[i].cost
				}
			}
			return 0;
		}
		
		private function seekNodeByIndex(index:String):nodeStruct
		{
			for(var i:int=0;i<_nodeList.length;i++)
			{
				if(_nodeList[i].index == index)
				{
					return _nodeList[i];
				}
			}
			
			return null;
		}
		
		private function generateNodeList():void
		{
			var len:int = _nodeIndexList.length;
			for(var i:int=0;i<len;i++)
			{
				var node:nodeStruct = seekNode(_nodeIndexList[i]);
				if(node != null)
				{
					_nodeList.push(node);
				}
			}
		}
		
		private function seekNode(index:String):nodeStruct
		{
			var len:int=_pathList.length;
			var pathNode:nodePathStruct;
			var node:nodeStruct = new nodeStruct();
			node.index = index;
			for(var i:int=0;i<len;i++)
			{
				pathNode = _pathList[i];
				if(pathNode.startIndex == index)
				{
					node.linkNodeList.push({index:pathNode.endIndex,cost:pathNode.cost});
				}else if(pathNode.endIndex == index)
				{
					node.linkNodeList.push({index:pathNode.startIndex,cost:pathNode.cost});
				}
			}
			
			return node;
		}
		
		private function generateNodeIndexList():void
		{
			var len:int = _pathList.length;
			var tempNodePath:nodePathStruct;
			for(var i:int=0;i<len;i++)
			{
				tempNodePath = _pathList[i];
				checkIsNewNode(tempNodePath.startIndex,tempNodePath.endIndex);
			}
		}
		
		private function checkIsNewNode(startIndex:String,endIndex:String):void
		{
			var isStartNew:Boolean = true;
			var isEndNew:Boolean = true;
			var len:int = _nodeIndexList.length;
			for(var i:int = 0;i<len;i++)
			{
				if(_nodeIndexList[i] == startIndex && _nodeIndexList[i] == endIndex)
				{
					isStartNew = false;
					isEndNew = false;
					break;
				}else if(_nodeIndexList[i] == startIndex)
				{
					isStartNew = false;
				}else if(_nodeIndexList[i] == endIndex)
				{
					isEndNew = false;
				}
			}
			if(isStartNew)
			{
				_nodeIndexList.push(startIndex);
			}else if(isEndNew)
			{
				_nodeIndexList.push(endIndex);
			}
		}
		
		private function generateNodePath(startIndex:String,endIndex:String,cost:uint):nodePathStruct
		{
			var nodePath:nodePathStruct = new nodePathStruct();
			nodePath.cost = cost;
			nodePath.startIndex = startIndex;
			nodePath.endIndex = endIndex;
			return nodePath;
		}
		
		public function get shortPath():Object
		{
			return _shortPath;
		}
		
		public function get addPath():Array
		{
			return _addPath;
		}
		
		public function get removePath():Array
		{
			return _removePath;
		}
		
	}
}
class nodePathStruct
{
	public var cost:uint;
	public var startIndex:String;
	public var endIndex:String;
}

class nodeStruct
{
	public var index:String;
	public var parentNodeIndex:String;
	public var parentNodeCost:uint;
	public var isVisiting:Boolean;
	public var linkNodeList:Array = [];
	public function get nodeType():int
	{
		if(index.charCodeAt(0) > 57)
		{
			return 1//为地点类型
		}else
		{
			return 2//为景点类型
		}
	}
}

